package solver;

import javafx.concurrent.Task;
import model.SlidingBox;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class PuzzleSolver extends Task<SlidingBox> {
    /**
     * 待处理的下一步状态，通过判别逻辑进一步决定要不要放进已知集里
     */
    private Deque<SlidingBox> workflow;
    /**
     * 已知状态集，存放着从初始状态计算出当前最小步数的状态
     */
    private List<SlidingBox> completed;
    /**
     * 初始状态
     */
    private SlidingBox startStep;

    public PuzzleSolver(SlidingBox startStep) {
        this.startStep = startStep;
        this.workflow = new LinkedList<>();
        this.completed = new LinkedList<>();
    }

    @Override
    protected SlidingBox call() {
        this.updateMessage("开始求解");
        return this.bfs();
    }

    /**
     * 从初始状态开始构造状态图
     */
    private SlidingBox bfs() {
        this.completed.add(startStep);
        this.workflow.addAll(startStep.getNextSteps());
        //弹出一个候选状态
        SlidingBox candidateStep = this.workflow.poll();
        while (candidateStep != null) {
            //更新状态
            this.updateValue(candidateStep);
            //成功求解
            if (candidateStep.succeeded()) {
                this.updateMessage("求解完成，需要移动的的步数为:" + candidateStep.getSteps());
                return candidateStep;
            }
            SlidingBox existingSlidingBox = null;
            //寻找候选状态是否已知
            for (SlidingBox completedSlidingBox : this.completed) {
                if (completedSlidingBox.equals(candidateStep)) {
                    existingSlidingBox = completedSlidingBox;
                    break;
                }
            }
            //如果存在说明找到一条通往已知结点的通路
            if (existingSlidingBox != null) {
                //候选状态的步数更少
                if (candidateStep.getSteps() < existingSlidingBox.getSteps()) {
                    //把状态集中
                    existingSlidingBox.setSteps(candidateStep.getSteps());
                    existingSlidingBox.setPrevSlidingBox(candidateStep.getPrevSlidingBox());
                }
            } else {
                //这是一个不存在的新状态
                this.completed.add(candidateStep);
                this.workflow.addAll(candidateStep.getNextSteps());
            }
            candidateStep = this.workflow.poll();
        }
        //未找到解法则返回空值
        this.updateMessage("求解结束，没有找到解法.");
        return null;
    }
}
